User blog:Alemagno12/Ordinals in CGT
In Combinatorial Game Theory (CGT), we can assign values to games that satisfy the following conditions: #The game is a 2-player game (the players are called Left and Right) #There are many possible positions, and often a particular starting position. #There are rules that specify the moves that either player can make from it's current position to it's options. #Left and Right alternate turns through the whole game. #Both players know what is going on. There is no missing information. #There are no chance moves. #If a player is unable to move in its turn, that player loses. #There is always a winner. There are a lot of values that can be assigned to positions in those games, but for now, we will only need to know two values: *A position X has value 0''' if whoever makes the first move (if the starting position of the game is X) loses the game (if both players play optimally) *A position X has value '''* if whoever makes the first move (if the starting position of the game is X) wins the game (if both players play optimally) We also have a notation for the values of games: {x|y}, where x would be the value of the game if Left makes a move, and y would be the value of the game if Right makes a move (if both players play optimally). An already lost game is represented with an empty space. Now, consider this game (which we will call the ordinal game) #Every position is an ordinal. #In its turn, a player can decrease the ordinal by 1 if it's a sequence ordinal. #In its turn, a player can change an ordinal to any term of it's fundamental sequence if the ordinal is a limit ordinal. #The smallest possible ordinal is 0. We say that an ordinal has '''game value '''n if that position in the ordinal game has value n. Now, time to calculate some game values of ordinals. Up to ??? 0 has game value 0, since no player can make a move. 1 has game value *, since when the first player moves, he/she will move to a position with value 0, which the second player will start and, therefore, lose, which means that the first player wins. 2 has game value 0, since when the first player moves, he/she will move to a position with value *, which the second player will start and, therefore, win, which means that the first player loses. In general: *{|} = 0, {0|0} = *, and {*|*} = 0. *Therefore, odd numbers have value * and even numbers have value 0. Now, what is the game value of ω? Well, the first player can just change ω to an even number (since the FS of ω is made up of all positive integers), which will have game value 0. So ω = {0|0} = *. We can also write this as sup(0,*,0,*,0,...) = *. Then, ω+1 has game value 0, ω+2 has game value *, and ω+x has game value 0 if x is odd and * if x is even. Then, ω2 has game value * because of the same reason why ω has game value *, and in general, ωn has game value * and ωn+m has game value 0 if m is odd and * if m is even (n > 0) Now, what is the game value of ω2? The first player has to change ω2 to an ordinal of the form ωn, which can have value 0 if n = 0 or * otherwise. The first player will obviously not change ω2 to *, since then he/she would lose, so he/she would change ω2 to 0. Therefore, ω2 has game value *. WIP Category:Blog posts